package LinkedList;

public class LeetCode_19_removeNthFromEnd {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        //定义一个假节点，用于返回结果
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //定义两个指针，一个快指针，一个慢指针
        ListNode prev = dummy;
        ListNode tail = dummy;
        //快指针先走n步
        while (n>0){
            prev = prev.next;
            n -- ;
        }
        //快慢指针一起走，只要快指针的next不为null就一直走
        while (prev.next != null){
            prev = prev.next;
            tail = tail.next;
        }
        tail.next = tail.next.next;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(3);
        listNode.next.next.next = new ListNode(4);
        listNode.next.next.next.next = new ListNode(5);
        ListNode node = removeNthFromEnd(listNode, 2);

        while (node!=null){
            System.out.println(node.val);
            node = node.next;
        }

    }
}
